package xiaomi;

public class Main1 {
    public static void main(String[] args) {

        String s="0011";
        System.out.println(minFlips(s));
//        System.out.println(minFlips2(s));
    }
     public static int minFlips(String s){
        int n=s.length();
        int[][] dp=new int[n][n];
        for(int i=0;i<n;++i){
            if(i==0){
                for(int t=0;t<n;++t){
                    dp[0][t]=0;
                }
                continue;
            }
            dp[i][0]=i;
            for(int j=1;j<n;j++){
                if (s.charAt(i) == s.charAt(n - j)) {
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    dp[i][j]=dp[i-1][j-1]+2;
                }
            }
        }
        int minFlips=Integer.MAX_VALUE;
        for(int j=0;j<n;++j){
            minFlips=Math.min(minFlips,dp[n-1][j]+j);
        }
        return minFlips;
     }

    public static int minFlips1(String s) {
        int count = 0;
        int n = s.length();

        // Count the number of different characters
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) != s.charAt(i - 1)) {
                count++;
            }
        }

        // Minimum flips would be the minimum of count and n - count
        return Math.min(count, n - count);
    }

    public static int minFlips2(String s) {
        int n = s.length();
        int[] prefixSum = new int[n + 1];

        // Calculate the prefix sum of differences between adjacent characters
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + (s.charAt(i) == '1' ? 1 : -1);
        }

        int minFlips = Math.abs(prefixSum[n]); // Initialize with total number of differences

        // Iterate through all possible split points and find the minimum flips
        for (int i = 0; i < n; i++) {
            minFlips = Math.min(minFlips, Math.abs(prefixSum[i] - prefixSum[n]));
        }

        return minFlips;
    }
}
